1. Field of the Invention
The present invention relates to a data driven type information processor, and more particularly, to a data driven type information processor having an improved function to read program data and an improved program execution efficiency.
2. Description of the Background Art
Parallel processing is employed in order to realize high speed information processing. Data driven type architecture has particularly attracted attention among parallel processing architecture.
In a data driven type processor, processing proceeds according to a rule "when all the data needed for a processing are available, and resources such as an operation apparatus required for the processing are assigned thereto, the processing is carried out".
FIG. 26 is a block diagram showing a conventional data driven type processor.
FIG. 27 is a diagram showing a format of a data packet applied to the conventional data driven type processor and embodiments of the present invention.
Referring to FIG. 27, the data packet includes a destination node number field F1 for storing a destination node number ND#, a generation number field F2 for storing a generation number GN#, an operation code field F3 for storing an operation code OPC, and a data field F4 for storing data DATA.
Referring to FIG. 26, a data driven type processor Pe includes a junction unit JNC, a firing control unit FC, an operation unit FPP, a program storage unit PSP, a branch unit BRN, a plurality of latch units, and a plurality of C(Cn) elements (packet transfer circuits).
FIG. 28 is a block diagram showing the program storage unit PSP. The program storage unit PSP having its input stage provided with a latch unit includes a program memory 200, an address generation and access unit 201, and a copy decision unit 202.
FIG. 29 is a diagram partially showing the contents of program memory 200 shown in FIG. 28.
A data flow program consisting of a plurality of program word sets Ws is prestored in program memory 200. Each program word set W is constituted by a subsequent node number ND#, a subsequent operation code OPC, and a copy flag cpy.
Each of the C elements shown in FIG. 26 controls data packet transfer of a corresponding processing unit by transmitting and receiving a data packet transfer pulse to and from C elements in the previous stage and in the subsequent stages thereof.
The data packet transfer pulse consists of signals of two kinds, that is, a SEND signal SD and a ACK (ACKnowledge) signal AK. The SEND signal SD is transferred from a C element in the previous stage of each C element to a C element in the subsequent stage thereof. Fall of the SEND signal SD indicates that a processing unit in the previous stage is ready to transfer a data packet.
The ACK signal AK is transferred from a C element in the subsequent stage of each C element to a C element in the previous stage thereof. The ACK signal AK at a "1" level indicates that a processing unit in the subsequent stage is ready to receive a data packet.
Accordingly, these two signals retained at a "1" level indicate that there is no data packet.
Each latch unit, in response to reception of a pulse from a corresponding C element, introduces and holds data received from a processing unit in the previous stage thereof, carries the data to an output stage thereof, and holds the data until the next pulse is received.
Referring to FIG. 26, when the processor Pe receives a data packet of FIG. 27, the received data packet is first applied through junction unit JNC to firing control unit FC. Firing control unit FC receives the data packet, and forms paired data of different data packets having the same destination node number ND# and the same generation number GN# if an operation code OPC of the received data packet is a prescribed operation code. More specifically, firing control unit FC detects two different data packets having the same node number ND# and the same generation number GN#, additionally stores data DATA of one data packet out of these two data packets having the same node number and the same generation number in a data field F4 of the other data packet, and outputs the other data packet. On the other hand, when the operation code of the received data packet is not the prescribed operation code, the received data packet is output directly.
The data packet output from firing control unit FC is then applied to operation unit FPP.
Operation unit FPP receives an applied data packet, decodes an operation code OPC of the received data packet, performs a prescribed operation of the contents of the received data packet based on the result of decoding, and stores the operation result in a data field F4 of the received data packet. The received data packet is then applied to program storage unit PSP.
Program storage unit PSP receives an applied data packet, and fetches the subsequent program data from program memory 200.
In this fetch of program data, when program storage unit PSP receives a data packet, address generation and access unit 201 generates an address adr from a destination node number ND# of the received data packet, and reads a program word set W from program memory 200 by addressing based on the address adr, as shown in FIG. 28. Then, a destination node number ND# and an operation code OPC in the read program word set W are stored in a destination node number field F1 and an operation code field F3 of the received data packet, respectively.
At this time, if a copy flag cpy corresponding to the read program word set W is "1", the subsequent address is concluded to be valid, so that a destination node number ND# and an operation code OPC of the subsequent address is stored similarly in the received data packet by addressing based on the subsequent address.
Accordingly, when a copy flag cpy is "1", two data packets for respective program word sets Ws of an address corresponding to the copy flag cpy and the subsequent address are generated and output (which is called "packet copy"). When a copy flag cpy is "0", only one data packet for an address corresponding to the copy flag cpy is output.
In packet copy, copy decision unit 202 makes a decision about a read copy flag cpy, and sends a copy request signal CR (=1) to a corresponding Cn element.
The Cn element which has received a copy request signal CR outputs a pulse for the first data packet transfer to a corresponding latch unit, and then outputs a Next Enable signal NE to address generation and access unit 201.
Then, after an appropriate time period, the Cn element outputs a pulse for the next data packet transfer to a corresponding latch unit, so that data accessed with an address incremented by one by address generating and access unit 201 in response to the Next Enable signal NE, that is, a program word set W stored in the subsequent address is latched and another data packet is transferred.
A data packet output from program storage unit PSP is applied to branch unit BRN, and the applied data packet is output from branch unit BRN or is returned to the processor based on a destination node number ND# thereof.
When branch processing such as selection of one of a plurality of instructions is performed in a data driven type processor Pe as described above, such an operation code SWN as disclosed in Japanese Patent Laying-Open No. 5-174167 is used. If this operation code SWN is used, a destination node number ND# of a received data packet is manipulated in operation unit FPP, whereby addressing based on a resultant destination node number ND# is carried out at the time of accessing program memory 200 in program storage unit PSP in the subsequent stage, and therefore, one of a plurality of program word sets W can be accessed selectively.
FIG. 30 is a conventional flow graph including a selection structure using a operation code SWN.
FIG. 31 is a diagram showing the contents of program memory 200 for the flow graph shown in FIG. 30.
FIG. 32 is a table obtained in the course of processing executed according to the flow graph shown in FIG. 30.
The flow graph shown in FIG. 30 includes nodes n1-n8 to which respective operation codes are assigned. An operation code ADD indicates that the result of adding right input data and left input data to a node to which the operation code is assigned is to be output. An operation code EQ indicates that 1 is to be output if left input data=right input data (=0, in the case of FIG. 30) to a node to which the operation code is assigned, and 0 is to be output if the left input data.noteq.the right input data. An operation code GE indicates that 1 is to be output if left input data.gtoreq.right input data to a node to which the operation code is assigned, and 0 is to be output if the left input data&lt;the right input data. An operation code SWN indicates that left input data to a node to which the operation code is assigned is added to a destination node number ND# of right input data thereto, and output is branched according to a resultant destination node number ND#.
The flow graph of FIG. 30 shows a processing in which an operation code Opr0 of node n6 is selected if the result of addition performed according to an operation code ADD of node n1 is smaller than 0, an operation code Opr1 of node n7 is selected if the addition result is larger than 0, and an operation code Opr2 of node n8 is selected if the addition result is equal to 0.
Since the operation of junction unit JNC, firing control unit FC and branch unit BRN at the time of executing a program according to the flow graph of FIG. 30 is the same as that described above, description thereof will not be repeated, and the operation of operation unit FPP and program storage unit PSP will now be described.
When operation unit FPP receives a data packet which stores a destination node number ND1 and an operation code ADD of node n1, paired data (right input data and left input data to node n1) in a data field F4 of the received data packet are added in operation unit FPP, the resultant value is stored in the data field F4 of the received data packet, and the received data packet is transferred to program storage unit PSP.
Thereafter, program storage unit PSP receives the transmitted data packet, and fetches the subsequent destination node number ND2 and the subsequent operation code EQ by addressing based on a destination node number ND1 of the received data packet, as shown in FIG. 31. At this time, since a corresponding fetched copy flag cpy=1, the subsequent address is valid and the subsequent destination node number ND3 and the subsequent operation code GE are fetched. Furthermore, since a corresponding copy flag cpy=1, the subsequent operation node number ND5 and the subsequent operation code SWN are fetched. Thus, three data packets each of which stores the fetched subsequent data and the addition result are applied to nodes n2, n3, and n5, respectively.
In node n2, output data is 1 if the addition result in an applied data packet=0 and an output data is 0 if the addition result.noteq.0.
In node n3, output data is 0 if the addition result in an applied data packet&lt;0, and output data is 1 if the addition result.gtoreq.0.
Thus, the relationship between the addition result in node n1 and left input data and right input data to node n4, as well as a result (output data) obtained in node n4 are such as shown in FIG. 32.
Referring to FIG. 32, in node n5, an offset of 1 is added to a destination address of left input data if the result of node n1 is positive, an offset of 2 is added thereto if 0, and an offset of 0 is added thereto if negative.
Thus, in the case of a data packet having a code SWN and a node number ND5 as an operation code OPC and a destination node number ND#, an offset of right data (a resultant value of node n4) is added to the node number ND5 in operation unit FPP, and therefore, access to memory 200 is performed in program storage unit PSP using the resultant node number ND#. As described above, according to this document, branch processing in which any one of nodes n6-n8 is selected with a single instruction of an operation code SWN is performed.
Although packet copy according to a copy flag cpy is carried out in the course of a program in the above description, processing is performed as follows in the case where the packet copy is carried out at the beginning of the program.
FIG. 33 is a diagram illustrating conventional procedure of processing in the case where packet copy is carried out at the beginning of a program.
As described above, packet copy according to a copy flag cpy is performed in program storage unit PSP. Therefore, if packet copy is carried out at the beginning of a program, an operation code NOP (an instruction indicating that a data packet which stores the operation code is caused to pass through a processor without operation) is assigned in the first node of the flow graph as shown in (a) of FIG. 33, the contents shown in (b) of FIG. 33 are stored in program memory 200, a data packet shown in (c) of FIG. 33 is first applied to processor Pe, an NOP instruction is executed by means of the applied data packet, whereby the applied data packet is caused to pass through processor Pe and then is applied again to processor Pe.
In the above described conventional method of controlling execution of a program including a selection structure, operation nodes of multi-stages are required to produce a selection control signal, as shown. in FIG. 30. Therefore, the number of instructions to be executed increases, resulting in difficulty in improving execution efficiency of a data flow program.
In addition, if processing such as packet copy at the beginning of a program is carried out, an NOP instruction is conventionally executed by means of a data packet and the data packet must be made to pass through a processor, so that circulating data packets are generated excessively, resulting in difficulty in improving program execution efficiency.